/*
 *用结点n中“不在位”的数码个数，某节点中的“不在位”的数码个数越多，说明它离目标节点越远。
 *优先策略优先选择“不在位”的数码个数少的节点进行分支。
 */
#include "TEight.h"
#include "TList.h"
#include <iostream>
#include <cmath>
using namespace std;
#define X 3
#define MAX 100000
class LeaestUnPostionBFS:public TEight
{
private :
	int cost;
	bool repeat(TList<LeaestUnPostionBFS> &L) {
		int n = L.Getlen();
		for (int i = 0; i < n; i++)
			if (L.GetData(i) == *this)
				return true;;
		return false;
	}
	void printl(TList<LeaestUnPostionBFS> &L) {
		LeaestUnPostionBFS T = *this;
		if (T.last == -1)
			return;
		else {
			T = L.GetData(T.last);
			T.printl(L);
			T.printSelf();
		}
	}
	int getAbsoluteCost()//得到初始状态的绝对cost值，即不考虑移动步数，只考虑和目标的位置之差
	{
		int tempCost = 0;
		for(int i=1;i<=Num; i++)
		  if( target[i]!=0 )
			if(origin[i] != target[i])
				tempCost++;
		return tempCost;
	}
	LeaestUnPostionBFS getNextState(int head,int tail,TList<LeaestUnPostionBFS> &tList)
	{
		int leastCost = MAX;
		int father = -1;
		LeaestUnPostionBFS t ;
		t.setSpace(-1);
		while(head <= tail)
		{
		 for(int direction=0;direction<DirNum ; direction++)
		 {
			 LeaestUnPostionBFS tBFS = tList.GetData(head);
			 if(tBFS.hasExpand == true)
				 break;
			 int lastAbsoluteCost = tBFS.getAbsoluteCost();//未扩展前的绝对代价
			 if(tBFS.extend(direction) && tBFS.repeat(tList)==false)
			 {
				 int curAbsoluteCost = tBFS.getAbsoluteCost();
				 int tempCost = tBFS.cost - lastAbsoluteCost + curAbsoluteCost +1;

				 if(tempCost < leastCost)
				 {
					 leastCost = tempCost;
					 father = head;
					 t = tBFS;
				 }
			 }
		 }
		 head ++;
		}

		 if(leastCost == MAX)
			 return t;
		 else
		 {
			 t.cost = leastCost;
			 t.last = father;
			 return t;
		 }
	}
public :
	LeaestUnPostionBFS(int * _orgin, int *_target):TEight(_orgin,_target)
	{
		cost = getAbsoluteCost();
		cout<<"初始代价为："<<cost<<endl;
	}
	LeaestUnPostionBFS()
	{
	}

	virtual void search()
	{
		LeaestUnPostionBFS tBFS = *this;
		 TList<LeaestUnPostionBFS> tList;
		 tList.Append(tBFS);//初始状态入队列

		 int head =0,tail=0;
		 while(head <= tail)
		 {
			tBFS = getNextState(head, tail, tList);
			if (tBFS.getSpace() <= 0)//space<=0说明无法打到下一状态
				break;

			tList.Append(tBFS);
			tList.GetData(tBFS.last).hasExpand = true;
			tail++;

			if (tBFS.isFind() == true)
			{
				//找到了
				cout << "find!" << endl;
				tBFS.printl(tList);
				tBFS.printSelf();
				return;
			}
		 }
		 cout<<"无解！"<<endl;
	}
};


